
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <title>322.零钱兑换 · Gary的小窝</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.3">
        <meta name="author" content="Gary">
        
        
    
    <link rel="stylesheet" href="../gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-prism/prism-solarizedlight.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-search-pro/search.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-splitter/splitter.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-tbfed-pagefooter/footer.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchor-navigation-ex/style/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-fontsettings/website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-theme-comscore/test.css">
                
            
        

    

    

        
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">

    
    <link rel="next" href="72.html" />
    
    
    <link rel="prev" href="14.html" />
    

    </head>
    <body>
        
<div class="book">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        
    
        <li class="chapter " data-level="1.1" data-path="../">
            
                <a href="../">
            
                    
                    写在前面
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="./">
            
                <a href="./">
            
                    
                    Leetcode之旅
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.2.1" data-path="1.html">
            
                <a href="1.html">
            
                    
                    1.两数之和
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.2" data-path="2.html">
            
                <a href="2.html">
            
                    
                    2.两数相加
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.3" data-path="3.html">
            
                <a href="3.html">
            
                    
                    3.无重复字符的最长子串
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.4" data-path="4.html">
            
                <a href="4.html">
            
                    
                    4.寻找两个有序数组的中位数
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.5" data-path="6.html">
            
                <a href="6.html">
            
                    
                    6.Z字形变换
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.6" data-path="9.html">
            
                <a href="9.html">
            
                    
                    9.回文数
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.7" data-path="11.html">
            
                <a href="11.html">
            
                    
                    11.盛最多水的容器
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.8" data-path="12.html">
            
                <a href="12.html">
            
                    
                    12.整数转罗马数字
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.9" data-path="13.html">
            
                <a href="13.html">
            
                    
                    13.罗马数字转整数
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.10" data-path="14.html">
            
                <a href="14.html">
            
                    
                    14.最长公共前缀
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="1.2.11" data-path="322.html">
            
                <a href="322.html">
            
                    
                    322.零钱兑换
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.12" data-path="72.html">
            
                <a href="72.html">
            
                    
                    72.编辑距离
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="../flutter/">
            
                <a href="../flutter/">
            
                    
                    Flutter从入门到放弃
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.3.1" data-path="../flutter/dart1.html">
            
                <a href="../flutter/dart1.html">
            
                    
                    1.Dart语言(1)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.2" data-path="../flutter/dart2.html">
            
                <a href="../flutter/dart2.html">
            
                    
                    2.Dart语言(2)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.3" data-path="../flutter/widget1.html">
            
                <a href="../flutter/widget1.html">
            
                    
                    3.Flutter初始化
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.4" data-path="../flutter/containerText.html">
            
                <a href="../flutter/containerText.html">
            
                    
                    4.Container和Text组件
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.5" data-path="../flutter/image.html">
            
                <a href="../flutter/image.html">
            
                    
                    5.Image组件
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.6" data-path="../flutter/chapter2.html">
            
                <a href="../flutter/chapter2.html">
            
                    
                    6.Flutter 技术总结
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="../vue/">
            
                <a href="../vue/">
            
                    
                    Vue组件精讲
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.4.1" data-path="../vue/1.html">
            
                <a href="../vue/1.html">
            
                    
                    1.provide/inject
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4.2" data-path="../vue/2.html">
            
                <a href="../vue/2.html">
            
                    
                    2.手动实现broadcast和dispatch方法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4.3" data-path="../js/form.html">
            
                <a href="../js/form.html">
            
                    
                    3.自己动手实现带校验的Form表单组件
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="../js/">
            
                <a href="../js/">
            
                    
                    JavaScript进阶
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.5.1" data-path="../js/proxy.html">
            
                <a href="../js/proxy.html">
            
                    
                    1.Vue.js 3.0中的响应式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.2" data-path="../js/el.html">
            
                <a href="../js/el.html">
            
                    
                    2.Element UI 源码初探
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.3" data-path="../js/bind.html">
            
                <a href="../js/bind.html">
            
                    
                    3.bind的模拟实现
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.4" data-path="../js/proto.html">
            
                <a href="../js/proto.html">
            
                    
                    4.JS原型和原型链
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.5" data-path="../js/call.html">
            
                <a href="../js/call.html">
            
                    
                    5.模拟实现call和apply
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.6" data-path="../js/ui.html">
            
                <a href="../js/ui.html">
            
                    
                    6.使用Vue cli3搭建组件库并发布到 npm
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.7" data-path="../js/microFE.html">
            
                <a href="../js/microFE.html">
            
                    
                    7.记一次基于qiankun的微前端的改造
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5.8" data-path="../js/git.html">
            
                <a href="../js/git.html">
            
                    
                    8.Git的使用
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="../vueLibrary/">
            
                <a href="../vueLibrary/">
            
                    
                    基于Vue的PC端的组件库
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.6.1" data-path="../vueLibrary/1.html">
            
                <a href="../vueLibrary/1.html">
            
                    
                    1.环境搭建
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.7" data-path="../life/">
            
                <a href="../life/">
            
                    
                    网事杂谈
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.7.1" data-path="../life/1.html">
            
                <a href="../life/1.html">
            
                    
                    1.周杰伦专辑赏析--叶惠美
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.7.2" data-path="../life/2.html">
            
                <a href="../life/2.html">
            
                    
                    2.周杰伦专辑赏析--七里香
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
            本书使用 GitBook 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href=".." >322.零钱兑换</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <div id="anchor-navigation-ex-navbar"><i class="fa fa-navicon"></i><ul><li><span class="title-icon "></span><a href="#322-&#x96F6;&#x94B1;&#x5151;&#x6362;"><b></b>322. &#x96F6;&#x94B1;&#x5151;&#x6362;</a></li><li><span class="title-icon "></span><a href="#&#x4E00;-&#x9898;&#x76EE;&#x63CF;&#x8FF0;"><b></b>&#x4E00; &#x9898;&#x76EE;&#x63CF;&#x8FF0;</a></li><li><span class="title-icon "></span><a href="#&#x4E8C;-&#x89E3;&#x9898;&#x8FC7;&#x7A0B;"><b></b>&#x4E8C; &#x89E3;&#x9898;&#x8FC7;&#x7A0B;</a></li></ul></div><a href="#322-&#x96F6;&#x94B1;&#x5151;&#x6362;" id="anchorNavigationExGoTop"><i class="fa fa-arrow-up"></i></a><h1 id="322-&#x96F6;&#x94B1;&#x5151;&#x6362;"><a name="322-&#x96F6;&#x94B1;&#x5151;&#x6362;" class="anchor-navigation-ex-anchor" href="#322-&#x96F6;&#x94B1;&#x5151;&#x6362;"><i class="fa fa-link" aria-hidden="true"></i></a>322. &#x96F6;&#x94B1;&#x5151;&#x6362;</h1>
<h1 id="&#x4E00;-&#x9898;&#x76EE;&#x63CF;&#x8FF0;"><a name="&#x4E00;-&#x9898;&#x76EE;&#x63CF;&#x8FF0;" class="anchor-navigation-ex-anchor" href="#&#x4E00;-&#x9898;&#x76EE;&#x63CF;&#x8FF0;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E00; &#x9898;&#x76EE;&#x63CF;&#x8FF0;</h1>
<blockquote>
<p>&#x7ED9;&#x5B9A;&#x4E0D;&#x540C;&#x9762;&#x989D;&#x7684;&#x786C;&#x5E01; coins &#x548C;&#x4E00;&#x4E2A;&#x603B;&#x91D1;&#x989D; amount&#x3002;&#x7F16;&#x5199;&#x4E00;&#x4E2A;&#x51FD;&#x6570;&#x6765;&#x8BA1;&#x7B97;&#x53EF;&#x4EE5;&#x51D1;&#x6210;&#x603B;&#x91D1;&#x989D;&#x6240;&#x9700;&#x7684;&#x6700;&#x5C11;&#x7684;&#x786C;&#x5E01;&#x4E2A;&#x6570;&#x3002;&#x5982;&#x679C;&#x6CA1;&#x6709;&#x4EFB;&#x4F55;&#x4E00;&#x79CD;&#x786C;&#x5E01;&#x7EC4;&#x5408;&#x80FD;&#x7EC4;&#x6210;&#x603B;&#x91D1;&#x989D;&#xFF0C;&#x8FD4;&#x56DE; -1&#x3002;</p>
</blockquote>
<p>&#x793A;&#x4F8B;1&#xFF1A;</p>
<pre class="language-"><code>&#x8F93;&#x5165;: coins = [1, 2, 5], amount = 11
&#x8F93;&#x51FA;: 3 
&#x89E3;&#x91CA;: 11 = 5 + 5 + 1
</code></pre><p>&#x793A;&#x4F8B;2&#xFF1A;</p>
<pre class="language-"><code>&#x8F93;&#x5165;: coins = [2], amount = 3
&#x8F93;&#x51FA;: -1
</code></pre><p>&#x4F60;&#x53EF;&#x4EE5;&#x8BA4;&#x4E3A;&#x6BCF;&#x79CD;&#x786C;&#x5E01;&#x7684;&#x6570;&#x91CF;&#x662F;&#x65E0;&#x9650;&#x7684;&#x3002;</p>
<h1 id="&#x4E8C;-&#x89E3;&#x9898;&#x8FC7;&#x7A0B;"><a name="&#x4E8C;-&#x89E3;&#x9898;&#x8FC7;&#x7A0B;" class="anchor-navigation-ex-anchor" href="#&#x4E8C;-&#x89E3;&#x9898;&#x8FC7;&#x7A0B;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E8C; &#x89E3;&#x9898;&#x8FC7;&#x7A0B;</h1>
<p>&#x8FD9;&#x9053;&#x9898; &#x5176;&#x5B9E;&#x7B97;&#x662F;&#x52A8;&#x6001;&#x89C4;&#x5212;&#x4E2D;&#x6BD4;&#x8F83;&#x7B80;&#x5355;&#x7684;&#x90A3;&#x79CD;&#x7C7B;&#x578B;&#x4E86;&#x3002;&#x56E0;&#x4E3A; &#x72B6;&#x6001;&#x53EA;&#x6709;&#x4E00;&#x4E2A;amount&#x3002; &#x6211;&#x4EEC;&#x8BBE;&#x5B9A;&#xFF1A; dp[n] &#x8868;&#x793A; &#x5F53;&#x524D;&#x7684;&#x76EE;&#x6807;&#x91D1;&#x989D;&#x662F; n&#xFF0C;&#x81F3;&#x5C11;&#x9700;&#x8981; dp(n) &#x4E2A;&#x786C;&#x5E01;&#x51D1;&#x51FA;&#x8BE5;&#x91D1;&#x989D;&#x3002;</p>
<p>&#x7136;&#x540E;&#x786E;&#x5B9A;&#x300C;&#x9009;&#x62E9;&#x300D;&#x5E76;&#x62E9;&#x4F18;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x5BF9;&#x4E8E;&#x6BCF;&#x4E2A;&#x72B6;&#x6001;&#xFF0C;&#x53EF;&#x4EE5;&#x505A;&#x51FA;&#x4EC0;&#x4E48;&#x9009;&#x62E9;&#x6539;&#x53D8;&#x5F53;&#x524D;&#x72B6;&#x6001;&#x3002;&#x5177;&#x4F53;&#x5230;&#x8FD9;&#x4E2A;&#x95EE;&#x9898;&#xFF0C;&#x65E0;&#x8BBA;&#x5F53;&#x7684;&#x76EE;&#x6807;&#x91D1;&#x989D;&#x662F;&#x591A;&#x5C11;&#xFF0C;&#x9009;&#x62E9;&#x5C31;&#x662F;&#x4ECE;&#x9762;&#x989D;&#x5217;&#x8868; coins &#x4E2D;&#x9009;&#x62E9;&#x4E00;&#x4E2A;&#x786C;&#x5E01;&#xFF0C;&#x7136;&#x540E;&#x76EE;&#x6807;&#x91D1;&#x989D;&#x5C31;&#x4F1A;&#x51CF;&#x5C11;&#xFF1A;
&#x6700;&#x540E;&#x9009;&#x4E00;&#x4E2A;&#x6700;&#x5C0F;&#x7684;</p>
<pre class="language-"><code>for coin in coins:
 res = min(res, 1 + dp(n - coin))
</code></pre><p>&#x90A3;&#x4E48;base case&#x5462;&#xFF1F;</p>
<p>&#x663E;&#x7136;&#x76EE;&#x6807;&#x91D1;&#x989D;&#x4E3A; 0 &#x65F6;&#xFF0C;&#x6240;&#x9700;&#x786C;&#x5E01;&#x6570;&#x91CF;&#x4E3A; 0&#xFF1B;&#x5F53;&#x76EE;&#x6807;&#x91D1;&#x989D;&#x5C0F;&#x4E8E; 0 &#x65F6;&#xFF0C;&#x65E0;&#x89E3;&#xFF0C;&#x8FD4;&#x56DE; -1&#xFF1A; </p>
<p>&#x5B8C;&#x6574;&#x4EE3;&#x7801;&#x5982;&#x4E0B;</p>
<pre class="language-"><code class="lang-JavaScript">/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    let dp = Array.apply(null,{length:amount+1}).map(item=&gt;{return amount+1})
    dp[0] = 0;
    for(let i = 0 ; i &lt; dp.length ; i ++){
        // &#x5185;&#x5C42; for &#x5728;&#x6C42;&#x6240;&#x6709;&#x5B50;&#x95EE;&#x9898; + 1 &#x7684;&#x6700;&#x5C0F;&#x503C;
        for (let j = 0 ; j&lt; coins.length;j++) {
            // &#x5B50;&#x95EE;&#x9898;&#x65E0;&#x89E3;&#xFF0C;&#x8DF3;&#x8FC7;
            if (i - coins[j] &lt; 0) continue;
            dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
        }
    }
     return (dp[amount] == amount + 1) ? -1 : dp[amount];
};
</code></pre>
<footer class="page-footer"><span class="copyright">Copyright &#xA9; YoungGary 2019 all right reserved&#xFF0C;powered by Gitbook</span><span class="footer-modification">&#x8BE5;&#x6587;&#x4EF6;&#x4FEE;&#x8BA2;&#x65F6;&#x95F4;&#xFF1A;
2021-09-09 22:08:17
</span></footer>
                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="14.html" class="navigation navigation-prev " aria-label="Previous page: 14.最长公共前缀">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
                <a href="72.html" class="navigation navigation-next " aria-label="Next page: 72.编辑距离">
                    <i class="fa fa-angle-right"></i>
                </a>
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"322.零钱兑换","level":"1.2.11","depth":2,"next":{"title":"72.编辑距离","level":"1.2.12","depth":2,"path":"leetcode/72.md","ref":"leetcode/72.md","articles":[]},"previous":{"title":"14.最长公共前缀","level":"1.2.10","depth":2,"path":"leetcode/14.md","ref":"leetcode/14.md","articles":[]},"dir":"ltr"},"config":{"plugins":["theme-comscore","prism","-highlight","copy-code-button","search-pro","-search","-lunr","expandable-chapters","splitter","-sharing","tbfed-pagefooter","anchor-navigation-ex"],"styles":{},"pluginsConfig":{"tbfed-pagefooter":{"copyright":"Copyright &copy YoungGary 2019","modify_label":"该文件修订时间：","modify_format":"YYYY-MM-DD HH:mm:ss"},"prism":{"css":["prismjs/themes/prism-solarizedlight.css"],"lang":{"shell":"bash"}},"splitter":{},"search-pro":{},"fontsettings":{"theme":"white","family":"sans","size":2},"anchor-navigation-ex":{"associatedWithSummary":true,"float":{"floatIcon":"fa fa-navicon","level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"mode":"float","multipleH1":true,"pageTop":{"level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"printLog":false,"showGoTop":true,"showLevel":false},"theme-comscore":{},"copy-code-button":{},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false},"expandable-chapters":{}},"theme":"default","author":"Gary","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"Gary的小窝","language":"zh-hans","gitbook":"*","description":"Gary的小窝. 里面包含了个人撰写的技术文章"},"file":{"path":"leetcode/322.md","mtime":"2021-09-09T14:08:17.740Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2021-09-09T14:10:10.930Z"},"basePath":"..","book":{"language":""}});
        });
    </script>
</div>

        
    <script src="../gitbook/gitbook.js"></script>
    <script src="../gitbook/theme.js"></script>
    
        
        <script src="../gitbook/gitbook-plugin-copy-code-button/toggle.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/jquery.mark.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/search.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-splitter/splitter.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-theme-comscore/test.js"></script>
        
    

    </body>
</html>

